package com.shuang.dp14;
//
//class Solution {
//    //完全背包问题
//    public int change(int amount, int[] coins) {
//
//        //二维dp数组解决 dp[i][j] 表示在[0,i]的物品中任取放进容量为j的背包 装满容量j 有dp[i][j]种方法
//        int[][] dp = new int[coins.length][amount + 1];
//
//        //递推公式
//        //不放i和放i的方法和  dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]
//
//        //初始化 题目已知1 <= coins[i] <= 5000 没有0金额
//        //第一列容量为0一定只有不放这一种方法
//        for (int i = 0; i < coins.length; i++){
//            dp[i][0] = 1;
//        }
//
//        //第一行 容量为物品0的整数倍即可有一种方法装满 其余不是装不满就是装不下都为0
//        for (int j = 0; j <= amount; j++){
//            if (j % coins[0] == 0){
//                dp[0][j] = 1;
//            }
//        }
//
//        //遍历顺序 二维dp数组 都可以 下面先物品然后背包从前到后
//        for (int i = 1; i < coins.length; i++){
//            for (int j = 1; j <= amount; j++){
//                if (j < coins[i]){
//                    dp[i][j] = dp[i - 1][j];
//                } else {
//                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
//                }
//            }
//        }
//
//        return dp[coins.length - 1][amount];
//    }
//}

class Solution {
    //完全背包问题
    public int change(int amount, int[] coins) {
        //一维dp数组解决 dp[j]表示 容量为j的背包 有dp[j]种方法装满
        int[] dp = new int[amount + 1];

        //递推公式：dp[j] += dp[j-coins[i]];

        //初始化
        dp[0] = 1;

        //遍历 组合问题 只能先物品后背包从前到后
        for (int i = 0; i < coins.length; i++){
            for (int j = coins[i]; j <= amount; j++){
                dp[j] += dp[j - coins[i]];
            }
        }

        return dp[amount];
    }
}